package Greedy.leetcode;

/**
 * 1. 问题描述
 *      小区便利店正在促销，用 numExchange 个空酒瓶可以兑换一瓶新酒。你购入了 numBottles 瓶酒。
 *      如果喝掉了酒瓶中的酒，那么酒瓶就会变成空的。
 *      请你计算 最多 能喝到多少瓶酒。
 *
 * 2. 算法分析
 *      每轮总共可以剩余的酒瓶数量 = 兑换 + 无法兑换剩余的
 *      每次加上兑换的
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 换酒问题 {
    public static void main(String[] args) {

    }

    /**
     * 模拟法
     *      1. 每轮总共可以剩余的酒瓶数量 = 兑换 + 无法兑换剩余的
     *      2. 循环退出条件：剩余的 < numExchange
     * @param numBottles
     * @param numExchange
     * @return
     */
    public static int numWaterBottles1(int numBottles, int numExchange) {
        int total = numBottles;
        int reminder = 0;
        int canexchanges = 0;
        // 每轮下来剩余的酒瓶数量 = 能兑换的 + 无法兑换剩余下来的，一起参与下一次判断
        // reminder = numBottles % numExchange    canexchanges = numBottles / numExchange
        // 判断一下循环结束的条件是什么? 当前剩余的酒瓶数量 < numExchange
        while(numBottles >= numExchange) {
            reminder = numBottles % numExchange;
            canexchanges = numBottles / numExchange;
            total += canexchanges;
            numBottles = reminder + canexchanges;
        }
        return total;
    }

    /**
     * 数学法
     *  假设当前有n个瓶子，每s个瓶子可以换一个，问一共可以喝多少瓶酒?
     *  已知有s个瓶子可以换1瓶酒，相当于我们每换1瓶，消耗了s个瓶子，但是重新获取了
     *  一个瓶子，所以我们的总消耗为s-1，即纯粹消耗s-1个瓶子换一瓶，假设我们一共可以换t瓶
     *  纯粹的消耗为t(s-1),此时只需要求出小的t使得 n - t(s-1) < s
     *
     * @param numBottles
     * @param numExchange
     * @return
     */
    public static int numWaterBottles2(int numBottles, int numExchange) {
        return numBottles >= numExchange ? (numBottles - numExchange) / (numExchange - 1) + 1 + numBottles : numBottles;
    }
}
